1916F - Group Division - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fr first
#define sc second

long long n[2],m,n2,nn,ttl,dh[4069],fh[4069],pr[4069],ca[4069],sq[4069],zs;
vector<pair<long long,long long>> al[4069];
bitset<4069> vtd,vtd2,spc;
vector<long long> al3[4069];
multiset<long long> ms[4069];
bool r0;

void dbd(long long x,long long b4)
{
	long long i,sz=al[x].size(),l,p,mn=dh[x];
	
	vtd[x]=1;
	vtd2[x]=1;
	fh[x]=dh[x];
	for(i=0;i<sz;i++)
	{
		l=al[x][i].fr;
		p=al[x][i].sc;
		if(p==b4)
		{
			continue;
		}
		if(!vtd[l])
		{
			dh[l]=dh[x]+1;
			pr[l]=x;
			dbd(l,p);
			fh[x]=min(fh[x],fh[l]);
			al3[x].push_back(l);
			ms[x].insert(fh[l]);
		}
		else if(vtd2[l])
		{
			fh[x]=min(fh[x],dh[l]);
			al3[l].push_back(x);
			mn=min(mn,dh[l]);
		}
	}
	vtd2[x]=0;
	ms[x].insert(mn);
}

bool cmp(long long x,long long y)
{
	return dh[x]>dh[y];
}

void dtrv(long long x)
{
	long long i,sz=al3[x].size(),l;
	
	vtd[x]=1;
	ttl++;
	spc[x]=1;
	if(ttl>=n[0])
	{
		r0=1;
		return;
	}
	nn++;
	ca[nn]=x;
	sort(al3[x].begin(),al3[x].end(),cmp);
	for(i=0;i<sz;i++)
	{
		l=al3[x][i];
		if(!vtd[l]&&(fh[l]>=dh[x]||dh[l]==dh[x]+1))
		{
			dtrv(l);
			if(r0)
			{
				return;
			}
		}
	}
	nn--;
	if(pr[x])
	{
		ms[pr[x]].erase(ms[pr[x]].find(fh[x]));
		if(!vtd[pr[x]]&&(!nn||*ms[pr[x]].begin()>dh[ca[nn]]))
		{
			dtrv(pr[x]);
		}
	}
}

int main()
{
	long long t,rr,i,ii,k,l;
	
	scanf("%lld",&t);
	for(rr=0;rr<t;rr++)
	{
		scanf("%lld%lld%lld",n,n+1,&m);
		n2=n[0]+n[1];
		for(i=1;i<=n2;i++)
		{
			al[i].clear();
			vtd[i]=0;
			vtd2[i]=0;
			al3[i].clear();
			ms[i].clear();
			spc[i]=0;
		}
		for(i=1;i<=m;i++)
		{
			scanf("%lld%lld",&k,&l);
			al[k].push_back({l,i});
			al[l].push_back({k,i});
		}
		dh[1]=0;
		pr[1]=0;
		dbd(1,-1);
		for(i=1;i<=n2;i++)
		{
			vtd[i]=0;
		}
		ttl=0;
		nn=0;
		r0=0;
		dtrv(al3[1][al3[1].size()-1]);
		for(ii=0;ii<2;ii++)
		{
			zs=0;
			for(i=1;i<=n2;i++)
			{
				if(spc[i]==!ii)
				{
					zs++;
					sq[zs]=i;
				}
			}
			for(i=1;i<=zs;i++)
			{
				printf("%lld%c",sq[i]," \n"[i==zs]);
			}
		}
	}
}